import sys
import random

def gen(n, sparse):
	COMPLETE = 0;
	MIDDLE  = 1;
	RARE = 2;
	matrix = [[sys.maxint for x in range(0,n)] for y in range(0,n)]
	for x in range(0,n):
		matrix[x][x]=0
	
	ext = range(1,n)   
	ostov = [0]
	while len(ext)!=0: 
		i = random.randint(0,len(ext)-1)
		j = random.choice(ostov)
		ostov.append(ext[i])
		cost = random.randint(0,100)
		matrix[ext[i]][j], matrix[j][ext[i]] = cost, cost
		del(ext[i])
	
	emptys = [[i,j] for i in range(0,n) for j in range(i+1,n)
			  if matrix[i][j]==sys.maxint]
	if sparse == COMPLETE:
		fill_count = ((n-1)*(n-2))/2
	elif sparse == MIDDLE:
		fill_count = random.randint((n-1)*(n-8)/2, (n-1)*(n-4)/2)
	elif sparse == RARE:
		fill_count = random.randint(0,max(0,(n-1)*(n-8)/2))
	else:
		fill_count = random.randint(0,max(0,((n-1)*(n-2))/2-1))
		
	for i in range(0,fill_count):
		j =  random.randint(0,len(emptys)-1)
		x,y = emptys[j]
		cost = random.randint(0,100)
		matrix[x][y], matrix[y][x] = cost, cost;
		del(emptys[j])
		
	
	count = 0
	for i in xrange(0,n):
		for j in xrange(i+1,n):
			if(matrix[i][j] != sys.maxint):
				print "{I} {J}".format(I=str(i+1), J=str(j+1))
				count = count + 1
				
				
	print (count+0.0)/(n*(n+1)/2)
				
	
				
gen(10,5)